package com.yuw.oop;

public class QuickSortor {
    // 快速排序的数组对象
    private int[] arr;

    public QuickSortor(int[] arr) {
        this.arr = arr;
    }

    // 快速排序的行为

    /**
     * 进行快速排序
     */
    public void doQuickSort() {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 快速排序主体算法：分治+递归
     *
     * @param arr  被排序的数组
     * @param low  从左往右的下标（低位下标）
     * @param high 从右往左的下标（高位下标）
     */
    private void quickSort(int[] arr, int low, int high) {
        // 递归结束条件部分： low >= high
        if (low < high) {
            // 获取本次分治的位置
            int mid = quickSort_sub(arr, low, high);
            // 递归调用部分
            // 前半部分递归处理
            quickSort(arr, low, mid - 1);
            // 后半部分的递归处理
            quickSort(arr, mid + 1, high);
        }
    }

    /**
     * 快速排序算法中的分治处理
     *
     * @param arr  被排序的数组
     * @param low  从左往右的下标（低位下标）
     * @param high 从右往左的下标（高位下标）
     * @return 本次分治的中间基准值所在的下标位置
     */
    private int quickSort_sub(int[] arr, int low, int high) {

        // 1 获取本次排序的集合中的第一个元素作为基准值
        int flag = arr[low];
        // 左右间隔进行置换循环的结束条件时； low >= high
        while (low < high) {
            // 2 从右往左（从当前high下标往前）查找第一个比基准值小的元素，然后把基准值和当前位置的元素进行交换(low和high进行交换)
            // 从high往前查找第一个比基准值小的元素的位置
            while (low < high && arr[high] >= flag) {
                high--;
            }
            // low位置和high位置进行交换
            if (low < high) {
                arr[low] = arr[high];
            }

            // 3 从左往右（从当前low下标往后）查找第一个比基准值大的元素，然后把基准值和当前位置的元素进行交换(low和high进行交换)
            while (low < high && arr[low] <= flag) {
                low++;
            }
            // low位置和high位置进行交换
            if (low < high) {
                arr[high] = arr[low];
            }
        }
        // 分治交换循环结束之后，low >= high
        // 4 将基准值放入分治的中间位置
        arr[low] = flag;
        // 返回分治间隔元素的基准值
        return low;
    }
    // 打印排序结果

    /**
     * 打印数组内容
     */
    public void printSortedArr() {
        for (int eachValue : arr) {
            System.out.print("   " + eachValue);
        }
        // 换行
        System.out.println();
    }
}
